package 贪心;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/10 17:36
 */
public class lc2611老鼠与奶酪 {
}


/*
 先贴一个 别人的 动态规划的版本!
 */
class Solution {
    public int miceAndCheese(int[] reward1, int[] reward2, int k) {
        // dp，数据量太大，超内存
        int n = reward1.length;
        // dp[i][j]：第一只老鼠从i块奶酪中吃j块所能获得的最大分数
        int[][] dp = new int[n+1][k+1];
        // 初始化dp数组，当第一只老鼠需要吃的块数k为0时，n块奶酪所能得最大分数就是全由第二只老鼠吃掉（第一只老鼠不吃，那么只能是第二只老鼠都吃）。
        for(int i = 0; i < n; ++i){
            dp[i+1][0] = dp[i][0] + reward2[i];
        }
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < k; ++j){
                // 当第一只老鼠接下来需要吃的奶酪块数j等于剩余奶酪块数i的时候，相当于第一只老鼠从i块奶酪中吃j块(i==j)所能获得的最大分数，但是第一只老鼠必须要吃够全部块数j，所以此时剩余的i块奶酪必须都由第一只老鼠吃掉，也就是j==i时，i这块奶酪只能是第一只老鼠吃。
                if(j == i){ dp[i+1][j+1] = dp[i][j] + reward1[i];}
                else{
                    // 第i块奶酪，第一只老鼠吃或者不吃
                    dp[i+1][j+1] = Math.max(dp[i][j] + reward1[i], dp[i][j+1] + reward2[i]);
                }
            }
        }
        return dp[n][k];
    }
}
